/*
Subsets
Given a set of distinct integers, nums, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
	void subCore(vector<vector<int> > &result, int start, vector<int> &temp, vector<int>& nums)
	{
		if (start == nums.size())
		{
			result.push_back(temp);
			return;
		}

		subCore(result, start + 1, temp, nums);

		temp.push_back(nums[start]);
		subCore(result, start + 1, temp, nums);

		temp.pop_back();

	}


	vector<vector<int> > subsets(vector<int>& nums) {

		vector<vector<int> > result;
		vector<int> temp;

		sort(nums.begin(),nums.end());

		subCore(result, 0, temp, nums);

		

		return result;
	}
};

int main()
{
	cout << "Plese input the numbers:  " << endl;

	vector<int> nums;
	int n;
	while (cin>>n)
	{
		nums.push_back(n);
	}

	Solution s;

	vector<vector<int> > result;
	result = s.subsets(nums);

	cout << "result:" << endl;

	for (int i = 0; i < result.size(); i++)
	{
		for (int j = 0; j < result[j].size(); j++)
		{
			cout << result[i][j] << " ";
		}
		cout << endl;
	}

	system("pause");

	return 0;
}